package practise.alogrithm.introductionToAlogrithm.foundations;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * this problem is present in the chapter 4.1 and it comes from a stock question, for how to find out the most profit.
 */
public class MaxSubarrayProblem {

    /**
     * this is the simplest method,which just record the max profit, and the value
     * @param values
     * @return
     */
    public static Profit max(List<Integer> values){
        int currentMaxProfit = 0;
        int currentLowest = Integer.MAX_VALUE;
        Profit profit = new Profit();
        for(Integer value : values){
            // first we try to get the lowest for calculating latter higher profit
            if(currentLowest > value){
                currentLowest = value;
            }
            // if the profit is higher, we record it
            if(currentMaxProfit<(value - currentLowest)){
                currentMaxProfit = value - currentLowest;
                profit.setLowIndex(currentLowest);
                profit.setHighIndex(value);
                profit.setProfit(currentMaxProfit);
            }
        }
        return profit;
    }

    /**
     * this is the method for get the result from the max subarray, this is the method used in the book,
     * in this method, we need consider three condition, first the max sum in left sub, then right sub, then cross the left and right
     * so for this method if we use divide and conquer method, we need run in this three condition, and take care of the procedure for getting
     * max from cross, for the left part, we need to start from middle
     * @param values
     * @return
     */
    public static Profit maxFromChange(List<Integer> values){
        return null;
    }



    public static Profit maxFromChangesInDynamic(List<Integer> values){
        int maxProfit = 0;
        int sum =0;
        int start=0;
        Profit profit = new Profit();
        values = convertPriceIntoChanges(values);
        for(Integer value : values){

            if((sum+value)<value){
                sum=value;
                start = value;
            }
            else{
                sum+=value;
            }
            if(maxProfit<sum){
                maxProfit=sum;
                profit.setHighIndex(value);
                profit.setLowIndex(start);
                profit.setProfit(maxProfit);
            }
        }
        return profit;
    }

    public static List<Integer> convertPriceIntoChanges(List<Integer> values){
        List<Integer> changes = new ArrayList<>();
        int base = values.remove(0);
        int size = values.size();
        for(int i =0 ; i<size;i++){
            changes.add(values.get(0)-base);
            base = values.remove(0);
        }
        System.out.println(changes);
        return changes;
    }



    public static void main(String[] args){
        System.out.println(max(new ArrayList<Integer>(Arrays.asList( new  Integer[]{100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97}))));
        System.out.println(maxFromChangesInDynamic(new ArrayList<Integer>(Arrays.asList(new Integer[]{100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97}))));
    }


}

class Profit{
    private int lowIndex;
    private int highIndex;
    private int profit;

    public int getLowIndex() {
        return lowIndex;
    }

    public void setLowIndex(int lowIndex) {
        this.lowIndex = lowIndex;
    }

    public int getHighIndex() {
        return highIndex;
    }

    public void setHighIndex(int highIndex) {
        this.highIndex = highIndex;
    }

    public int getProfit() {
        return profit;
    }

    public void setProfit(int profit) {
        this.profit = profit;
    }

    @Override
    public String toString() {
        return "Profit{" +
                "lowIndex=" + lowIndex +
                ", highIndex=" + highIndex +
                ", profit=" + profit +
                '}';
    }
}
